以stack来进一步了解C语言的泛型

此篇博文根据斯坦福公开课 《编程范式》整理，也算是一个简单的笔记。

Stack（栈）

栈是一种十分基础的数据结构，也十分简单，下面我们首先来实现此种数据结构的int表示

stack.h

在此文件之中，我们对栈的结构和栈的基本操作进行了定义，其中代码如下：

typedef struct {
    int* elems;
    int logLength;
    int allocLength;
}stack;

void StackNew(stack* s);
void StackDispose(stack* s);
void StackPush(stack* s, int value);
int StackPop(stack* s);

stack.c

此文件中，将 .h 文件中的函数进行了实现，代码如下：

void StackNew(stack* s) {
    s->allocLength = 4;
    s->logLength = 0;
    s->elems = malloc(sizeof(int)*s->allocLength);
    assert(s->elems != NULL);
}

void StackDispose(stack* s) {
    free(s->elems);
}

void StackPush(stack* s, int value) {
    if (s->logLength == s->allocLength) {
        s->allocLength *= 2;
        s->elems = realloc(s->elems, s->allocLength*sizeof(int));
        assert(s->elems != NULL);
    }
    s->elems[s->logLength++] = value;
}

int StackPop(stack* s) {
    assert(s->logLength > 0);
    return s->elems[s->logLength--];
}

说明：

1. assert() ：存于 assert.h 头文件之中，其传参为一个布尔值，传入值为true 之时，什么也不做；如果为flase ，就停止继续执行程序并打印错误。用于此处，是为了检测开辟空间是否成功。
2. StackPush() 函数可以拓展栈的大小

如同之前所讲，有了基本的 int 版，那么就可以向着泛型版转化了。

泛型化的stack

为了向泛型进化，我们必须在原结构体中加入数据类型的字节数，所以结构体结果如下：

typedef struct {
    int* elems;
    int elemSize;
    int logLength;
    int allocLength;
}stack;

void StackNew(stack* s, int elemSize);
void StackDispose(stack* s);
void StackPush(stack* s, void* elemAddr);
void StackPop(stack* s, void* elemAddr);

同理，各个函数的写法如下：

void StackNew(stack* s, int elemSize) {
    assert(s->elems > 0);
    s->elemSize = elemSize;
    s->allocLength = 4;
    s->logLength = 0;
    s->elems = malloc(elemSize*s->allocLength);
    assert(s->elems != NULL);
}

void StackDispose(stack* s) {
    free(s->elems);
}

static void StackGrow(stack *s) {
    s->allocLength *= 2;
    s->elems = realloc(s->elems, s->elemSize * s->allocLength);
    assert(s->elems != NULL);
}

void StackPush(stack* s, void* elemAddr) {
    if (s->logLength == s->allocLength)
        StackGrow(s);
    void* target = (char*)s->elems + s->logLength*s->elemSize;
    memcpy(target, elemAddr, s->elemSize);
    s->logLength++;
}

void StackPop(stack* s, void* elemAddr) {
    int* source = (char*)s->elems + (s->logLength - 1) * s->elemSize;
    memcpy(elemAddr, source, s->elemSize);
    s->logLength--;
}

说明：

1. 值与值之间的传递都依靠参数传递
2. static 修饰的函数，只在当前文件可以调用（也就是相当于一个内部函数）

关于字符串

众所周知，字符串的传递是与众不同的，所以与其相关的一些问题也需要进行特殊处理，我们先来看一段使用字符串进行栈操作的代码：

int main() {
    const char* names[] = {"Bob", "Lily", "Mike", "James"};
    stack* s;
    char* name;
    StackNew(s, sizeof(char*));
    for(int i = 0; i < 4; i++) {
        char* copy = strdup(names[i]);
        StackPush(s, &copy);    
    }
    for(int i = 0; i < 4; i++) {
        StackPop(s, &name);
        printf("%s\n", name);
        free(name);
    }
    StackDispose(s);
    return 0;
}

由于字符串的长度是不一定的，为了简化代码，因此操作字符串之时在栈中保存的是指向该字符串的指针，但是如此一来便会产生一个问题：

当栈中还有元素之时，用户直接进行StackDispose() 操作之后，并没有释放掉指针所指向的空间，因此我们需要继续改进代码。

而怎样改进呢？首先我们应该让程序知道这个栈到底是什么类型的栈，如果是指针类型的，就要在结构体中传入一个额外的指针，指向栈所指向的地址，以便在之后更好地进行free()，所以将结构体改进如下：

typedef struct {
    int* elems;
    int elemSize;
    int logLength;
    int allocLength;
    void (*freefn) (void*);
}stack;

而我们在进行 StackNew() 操作之时，就需要对栈的类型进行声明，所以将其传参改进如下：

void StackNew(stack* s, int elemSize; void* freefn(void*)) {
    assert(s->elems > 0);
    s->freefn = freefn;
    s->elemSize = elemSize;
    s->allocLength = 4;
    s->logLength = 0;
    s->elems = malloc(elemSize*s->allocLength);
    assert(s->elems != NULL);
}

同时，我们将对 StackDispose() 进行重写：

void StackDispose(stack* s) {
    if (s->freefn != NULL) {
        for (int i = 0; i < s->logLength; i++) {
            s->freefn ((char*)s->elems + i * s->elemSize);
        }
    }
    free(s->elems);
}

一般来说，字符串的释放函数应当如下：

void StrFree(void *s) {
    free(*(char**)s);
}